package first.niuke.midding;

/**
 * @ClassName NC17
 * @description:
 * @author: 荣燊
 * @create: 2021-06-19 14:05
 **/
public class NC17 {
    public static void main(String[] args) {

    }

    // 最长回文字符串
    public int getLongestPalindrome(String A, int n) {
        // write code here
        // dp[i][j]表示第i个字符到第j个字符是否是回文字符串
        boolean[][] dp = new boolean[n][n];
        int max = 0;

        // 字符串首尾字母长度差: d=j-i
        for (int d=0; d<n; d++) {
            // 字符串起始位置i
            for (int i=0; i<n-d; i++) {
                int j = i+d;
                if (A.charAt(i) == A.charAt(j)) {
                    // 如果首位只差0或1位
                    if (d == 0 || d == 1) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i+1][j-1];
                    }
                    if (dp[i][j]) {
                        max = Math.max(max, d+1);
                    }
                }

            }
        }
        return max;
    }
}
